package com.yjz.leetcode.LRU算法;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * HashMap 与 LinkedList 实现Lru
 * @param <K>
 * @param <V>
 */
public class Lru<K, V> {
    private int capacity;
    private Map<K, V> cache;
    private LinkedList<K> list;

    public Lru(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.list = new LinkedList();
    }

    public V get(K k) {
        if (cache.containsKey(k)) {
            //删除原来的
            list.remove(k);
            //每一次使用都从头插入
            list.addFirst(k);
            return cache.get(k);
        }
        return null;
    }

    public void put(K k, V v) {
        if (cache.containsKey(k)) {
            list.remove(k);
            //头插
            list.addFirst(k);
            cache.put(k, v);
        } else if (capacity == list.size()) {
            //链表尾部的key移除
            cache.remove(list.removeLast());
            //头插
            list.addFirst(k);
            cache.put(k, v);
        } else {
            list.addFirst(k);
            cache.put(k, v);
        }
    }

    @Override
    public String toString() {
        return "Lru{" +
                "capacity=" + capacity +
                ", cache=" + cache +
                ", list=" + list.toString() +
                '}';
    }

    public static void main(String[] args) {
        Lru<String, String> lru = new Lru(4);
        lru.put("name","张三");
        lru.put("age","15");
        lru.put("sex","男");
        lru.put("weight","150斤");
        System.out.println("**没有超过容量的情况******");
        System.out.println(lru);
        lru.put("height","150cm");
        System.out.println("**最开始的name应该被剔除了*******");
        System.out.println(lru);
        System.out.println("取一个过期的key->name:"+lru.get("name"));
        System.out.println("取一个老key->weight:"+lru.get("weight"));
        System.out.println(lru);
    }

}
